#include "leetcode_util.h"

int helper1(string& A, int as, int ae, string& B, int bs, int be, int count) {
    if (as == ae) {
        return count + be - bs;
    }
    if (bs == be) {
        return count + ae - as;
    }
    if (A[as] == B[bs]) {
        return helper1(A, as+1, ae, B, bs+1, be, count);
    }
    // kitten -> sitting
    // case1 s+kitten -> sitting ==> kitten -> itting
    int case1 = helper1(A, as, ae, B, bs+1, be, count+1);
    // case2 [k->s]itten -> sitting
    int case2 = helper1(A, as+1, ae, B, bs+1, be, count+1);
    // case3 k|itten -> sitting
    int case3 = helper1(A, as+1, ae, B, bs, be, count+1);

    return min(min(case1, case2), case3);
}

int solution1(string A, string B) {
    int la = A.size(), lb = B.size();
    return helper1(A, 0, la, B, 0, lb, 0);
}


/*
# replace insert
# delete  HERE
### From "ephrem" to "benyam"
#   | " | b | e | n | y | a | m |
# " | 0 | 1 | 2 | 3 | 4 | 5 | 6 | # From "" to "benyam" (insert)
# e | 1 | ? = min(""->"b"+1, ""->""+1, "b"->""+1)
# p | 2 |
# h | 3 |
# r | 4 |
# e | 5 |
# m | 6 |
# From "ephrem" to ""
def TheLevenshteinDistanceDP(a, b):
    la = len(a)
    lb = len(b)
    if la == 0:
        return lb
    if lb == 0:
        return la
    dp = [[0 for y in range(lb+1)] for x in range(la+1)]
    for i in range(la+1):
        for j in range(lb+1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            else:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
                if a[i-1] != b[j-1]:
                    dp[i][j] += 1
    return dp[la][lb]
*/

void showVector(vector<int>& A) {
    vector<int>::iterator itr = A.begin();
    for(; itr != A.end();) {
        printf("%d", *itr);
        if (++itr != A.end()) {
            printf(" ");
        } else {
            printf("\n");
        }
    }
}

void testVector(int argc, char *argv[]) {
    string s;
    for (int i = 1; i < argc; i++) {
        s = string(argv[i]);
        vector<int> v = stringToVector(s);
        // test function

        // cout << numberOfArithmeticSlices(v) << endl;
    }
}

int main(int argc, char *argv[]) {
    string a = "xabcd";
    string b = "abcdy";

    int result;
    int N = 1;
    clock_t c_start = clock();
    for (int i = 0; i < N; ++i) {
        result = solution1(a, b);
    }
    cout << "solution1: " << result << " - " << float( clock () - c_start ) /  CLOCKS_PER_SEC << endl;
    /*
    c_start = clock();
    for (int i = 0; i < N; ++i) {
        result = solution2(a, b);
    }
    cout << "solution2: " << result << " - " << float( clock () - c_start ) /  CLOCKS_PER_SEC << endl;
    c_start = clock();
    for (int i = 0; i < N; ++i) {
        result = solution3(a, b);
    }
    cout << "solution3: " << result << " - " << float( clock () - c_start ) /  CLOCKS_PER_SEC << endl;
    */
}

